#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/25 17:16
# ===========================================
#       题目名称： 40. 组合总和 II
#       题目地址： https://leetcode.cn/problems/combination-sum-ii/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================


class Solution:
    def combinationSum2(self, candidates, target):
        res = set()
        res_dict = dict()  # 返回值字典 key 已存在元素 排序后的 v 未排序元素
        # 初始化一下
        candidates.sort()
        for i in range(len(candidates)):
            if candidates[i] == target:
                res.add((candidates[i],))
            else:
                temp = candidates.copy()
                del temp[i]
                res_dict[(candidates[i],)] = temp
        while res_dict:
            temp_res_dict = dict()
            for k, v in res_dict.items():
                cur_k_res = 0  # 当前k累计的值
                for item in k:
                    cur_k_res += item
                for i in range(len(v)):
                    if v[i] > target - cur_k_res:  # 如果当前的值比剩余的值大 直接break
                        break
                    # print(v[i], cur_k_res, target - cur_k_res)
                    if v[i] == target - cur_k_res:
                        elements = list(k + (v[i],))
                        elements.sort()
                        res.add(tuple(elements))
                    else:
                        temp = v.copy()
                        del temp[i]
                        key = list(k + (v[i],))
                        key.sort()
                        temp_res_dict[tuple(key)] = temp
            res_dict = temp_res_dict
        return list(list(item) for item in res)


if __name__ == '__main__':
    s = Solution()
    # [[1,1,6],[1,2,5],[1,7],[2,6]]
    print(s.combinationSum2(candidates=[10, 1, 2, 7, 6, 1, 5], target=8))
    # [[1,2,2],[5]]
    print(s.combinationSum2(candidates=[2, 5, 2, 1, 2], target=5))
